home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / CODECS.ZIP / codecs / francais / dcodhuff.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-10-13  |  10.3 KB  |  272 lines
  1. /* Fichier: dcodhuff.c
  2.    Auteur: David Bourgin
  3.    Date de creation: 15/2/94
  4.    Date de derniere mise a jour: 24/7/95
  5.    Dessein: Exemple de decodage Huffman avec comme donnees a decompresser le contenu d'un fichier.
  6. */
  7.  
  8. #include <stdio.h>
  9. /* Pour les routines printf,fgetc,fputc */
  10. #include <memory.h>
  11. /* Pour la routine memset */
  12. #include <stdlib.h>
  13. /* Pour la routine exit */
  14. #include <malloc.h>
  15. /* Pour les routines malloc et free */
  16.  
  17. /* Codes d'erreur renvoyes a l'appelant */
  18. #define NO_ERROR       0
  19. #define BAD_FILE_NAME  1
  20. #define BAD_ARGUMENT   2
  21. #define BAD_MEM_ALLOC  3
  22.  
  23. /* Constantes pratiques */
  24. #define FALSE 0
  25. #define TRUE  1
  26.  
  27. typedef struct s_arbre { unsigned int octet;
  28.                              /* Un octet est volontairement code comme un entier non signe pour qu'un noeud fictif puisse depasser la valeur 255 */
  29.                          struct s_arbre *ptr_gauche,
  30.                                         *ptr_droit;
  31.                        } t_arbre,*p_arbre;
  32. #define OCTET_ARBRE(ptr_arbre)  ((*(ptr_arbre)).octet)
  33. #define PGAUCHE_ARBRE(ptr_arbre)  ((*(ptr_arbre)).ptr_gauche)
  34. #define PDROIT_ARBRE(ptr_arbre)  ((*(ptr_arbre)).ptr_droit)
  35.  
  36. typedef struct { unsigned char bits[32],
  37.                                nb_bits,
  38.                                presence;
  39.                } t_val_bin;
  40. #define BITS_VAL_BIN(x)  ((x).bits)
  41. #define NB_BITS_VAL_BIN(x)  ((x).nb_bits)
  42. #define PRESENCE_VAL_BIN(x)  ((x).presence)
  43.  
  44. /* Variables globales */
  45. FILE *f_source,*f_dest;
  46.  
  47.                              /* Puisque fgetc=EOF uniquement apres un acces
  48.                                 alors statut_octet_stocke vaut TRUE si un octet a ete engrange par fgetc
  49.                                 ou FALSE s'il n'y aucun octet valide, deja lu et non traite dans val_octet_stocke */
  50. int statut_octet_stocke=FALSE;
  51. int val_octet_stocke;
  52.  
  53. /* Pseudo procedures */
  54. #define fin_des_donnees() (statut_octet_stocke?FALSE:!(statut_octet_stocke=((val_octet_stocke=fgetc(f_source))!=EOF)))
  55. #define lire_octet()  (statut_octet_stocke?statut_octet_stocke=FALSE,(unsigned char)val_octet_stocke:(unsigned char)fgetc(f_source))
  56. #define ecrire_octet(octet)  ((void)fputc((octet),f_dest))
  57.  
  58. unsigned char nb_bits_a_lire=0;
  59. unsigned int val_a_lire=0;
  60.  
  61. unsigned char lire_code_1_bit()
  62. /* Parametres en sortie: Renvoie un entier non signe sur 1 bit valide (a droite de l'entier)
  63.    Action: Lit dans le fichier des donnees en entree le prochain bit
  64.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
  65.    La source des donnees doit disposer de suffisamment de bits restants a lire
  66. */
  67. { unsigned int resultat;
  68.  
  69.   if (nb_bits_a_lire)
  70.      { nb_bits_a_lire--;
  71.        resultat=(val_a_lire >> nb_bits_a_lire) & 1;
  72.      }
  73.   else { val_a_lire=lire_octet();
  74.          nb_bits_a_lire=7;
  75.          resultat=(val_a_lire >> 7) & 1;
  76.        }
  77.   val_a_lire &= 127;
  78.   return resultat;
  79. }
  80.  
  81. unsigned int lire_code_n_bits(n)
  82. /* Parametres en sortie: Renvoie un entier non signe sur 'n' bits valides (a droite de l'entier)
  83.    Action: Lit dans le fichier des donnees en entree les n prochains bits
  84.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
  85.    La source des donnees doit disposer de suffisamment de bits restants a lire
  86. */
  87. unsigned char n;
  88. { unsigned int resultat;
  89.  
  90.   while ((nb_bits_a_lire<n)&&(!fin_des_donnees()))
  91.         { val_a_lire = (val_a_lire << 8)+lire_octet();
  92.           nb_bits_a_lire += 8;
  93.         }
  94.   nb_bits_a_lire -= n;
  95.   resultat=val_a_lire >> nb_bits_a_lire;
  96.   val_a_lire &= ((1<<nb_bits_a_lire)-1);
  97.   return resultat;
  98. }
  99.  
  100. void lire_en_tete(table_codes)
  101. /* Parametres en sortie: Le contenu de 'table_codes' est modifie
  102.    Action: Reconstruit le tableau de codage binaire a partir de l'en-tete
  103.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
  104. */
  105. t_val_bin table_codes[257];
  106. { register unsigned int i,j;
  107.   char num_octet;
  108.  
  109.   (void)memset((char *)table_codes,0,257*sizeof(*table_codes));
  110.                              /* == Decodage de la premiere partie de l'en-tete == */
  111.   if (lire_code_1_bit())
  112.                              /* Premier bit=0 => Octets presents codes sur n*8 bits
  113.                                            =1 => Octets presents codes sur 256 bits */
  114.      for (i=0;i<=255;i++)
  115.          PRESENCE_VAL_BIN(table_codes[i])=lire_code_1_bit();
  116.   else { i=lire_code_n_bits(5)+1;
  117.          while (i)
  118.                { PRESENCE_VAL_BIN(table_codes[lire_code_n_bits(8)])=1;
  119.                  i--;
  120.                }
  121.        }
  122.   PRESENCE_VAL_BIN(table_codes[256])=1;
  123.                              /* La presence de l'octet fictif 256 est forcee! */
  124.  
  125.                              /* == Decodage de la seconde partie de l'en-tete == */
  126.   for (i=0;i<=256;i++)
  127.       if PRESENCE_VAL_BIN(table_codes[i])
  128.          { if (lire_code_1_bit())
  129.                              /* Premier bit=0 => 5 bits de longueur binaire-1 suivi du mot binaire
  130.                                            =1 => 8 bits de longueur binaire-1 suivi du mot binaire */
  131.               j=lire_code_n_bits(8)+1;
  132.            else j=lire_code_n_bits(5)+1;
  133.            NB_BITS_VAL_BIN(table_codes[i])=j;
  134.                              /* Lecture du mot binaire */
  135.            num_octet=(j+7) >> 3;
  136.            if (j & 7)
  137.               {              /* Lire les bits ne formant pas un octet */
  138.                 num_octet--;
  139.                 BITS_VAL_BIN(table_codes[i])[num_octet]=(unsigned char)lire_code_n_bits(j & 7);
  140.               }
  141.            while (num_octet)
  142.                  {           /* Lire les bits format un octet */
  143.                    num_octet--;
  144.                    BITS_VAL_BIN(table_codes[i])[num_octet]=(unsigned char)lire_code_n_bits(8);
  145.                  }
  146.          }
  147. }
  148.  
  149. void supprimer_arbre(arbre)
  150. /* Parametres en sortie: Aucun
  151.    Action: Supprime la memoire allouee a un arbre
  152.    Erreurs: Aucune si l'arbre a ete construit par allocations dynamiques!
  153. */
  154. p_arbre arbre;
  155. { if (arbre!=NULL)
  156.      { supprimer_arbre(PGAUCHE_ARBRE(arbre));
  157.        supprimer_arbre(PDROIT_ARBRE(arbre));
  158.        free(arbre);
  159.      }
  160. }
  161.  
  162. p_arbre coder_arbre(table_codes)
  163. /* Parametres en sortie: Un arbre binaire est renvoye
  164.    Action: Renvoie l'arbre binaire de decodage de 'table_codes'
  165.    Erreurs: Aucune
  166. */
  167. t_val_bin table_codes[257];
  168. { register unsigned int i;
  169.   unsigned int j;
  170.   p_arbre ptr_arbre,noeud_courant;
  171.  
  172.   if ((ptr_arbre=(p_arbre)malloc(sizeof(t_arbre)))==NULL)
  173.      exit(BAD_MEM_ALLOC);
  174.   OCTET_ARBRE(ptr_arbre)=257;
  175.   PGAUCHE_ARBRE(ptr_arbre)=NULL;
  176.   PDROIT_ARBRE(ptr_arbre)=NULL;
  177.   for (i=0;i<=256;i++)
  178.       { for (noeud_courant=ptr_arbre,j=NB_BITS_VAL_BIN(table_codes[i]);j;j--)
  179.           { if (BITS_VAL_BIN(table_codes[i])[(j-1) >> 3] & (1 << ((j-1) & 7)))
  180.                if (PGAUCHE_ARBRE(noeud_courant)==NULL)
  181.                   { if ((PGAUCHE_ARBRE(noeud_courant)=(p_arbre)malloc(sizeof(t_arbre)))==NULL)
  182.                        { supprimer_arbre(ptr_arbre);
  183.                          exit(BAD_MEM_ALLOC);
  184.                        }
  185.                     noeud_courant=PGAUCHE_ARBRE(noeud_courant);
  186.                     PGAUCHE_ARBRE(noeud_courant)=NULL;
  187.                     PDROIT_ARBRE(noeud_courant)=NULL;
  188.                   }
  189.                else noeud_courant=PGAUCHE_ARBRE(noeud_courant);
  190.             else if (PDROIT_ARBRE(noeud_courant)==NULL)
  191.                     { if ((PDROIT_ARBRE(noeud_courant)=(p_arbre)malloc(sizeof(t_arbre)))==NULL)
  192.                          { supprimer_arbre(ptr_arbre);
  193.                            exit(BAD_MEM_ALLOC);
  194.                          }
  195.                       noeud_courant=PDROIT_ARBRE(noeud_courant);
  196.                       PGAUCHE_ARBRE(noeud_courant)=NULL;
  197.                       PDROIT_ARBRE(noeud_courant)=NULL;
  198.                     }
  199.                  else noeud_courant=PDROIT_ARBRE(noeud_courant);
  200.             if (j==1)
  201.                OCTET_ARBRE(noeud_courant)=i;
  202.             else OCTET_ARBRE(noeud_courant)=257;
  203.           }
  204.       }
  205.   return (ptr_arbre);
  206. }
  207.  
  208. void decodagehuff()
  209. /* Parametres en sortie: Aucun
  210.    Action: Decompresse suivant la methode de Huffman tous les octets lus par les fonctions lire_code_1_bit et lire_code_n_bits
  211.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
  212. */
  213. { t_val_bin table_codage[257];
  214.   p_arbre ptr_arbre,noeud_courant;
  215.  
  216.   if (!fin_des_donnees())    /* Y a-t-il des donnees a compresser? */
  217.      { lire_en_tete(table_codage);
  218.        ptr_arbre=coder_arbre(table_codage);
  219.        do { noeud_courant=ptr_arbre;
  220.             while (OCTET_ARBRE(noeud_courant)==257)
  221.                   if (lire_code_1_bit())
  222.                              /* Bit=1 => Aller a gauche dans le noeud courant de l'arbre
  223.                                    =0 => Aller a droite dans le noeud courant de l'arbre */
  224.                      noeud_courant=PGAUCHE_ARBRE(noeud_courant);
  225.                   else noeud_courant=PDROIT_ARBRE(noeud_courant);
  226.             if (OCTET_ARBRE(noeud_courant)<=255)
  227.                ecrire_octet(OCTET_ARBRE(noeud_courant));
  228.           }
  229.        while (OCTET_ARBRE(noeud_courant)!=256);
  230.        supprimer_arbre(ptr_arbre);
  231.      }
  232. }
  233.  
  234. void aide()
  235. /* Parametres en sortie: Aucun
  236.    Action: Affiche l'aide du programme et termine son execution
  237.    Erreurs: Aucune
  238. */
  239. { printf("Cet utilitaire permet de decompresser un fichier par la methode de Huffman\n");
  240.   printf("telle qu'elle est exposee dans 'La Video et Les Imprimantes sur PC'\n");
  241.   printf("\nUsage: dcodhuff source destination\n");
  242.   printf("source: Nom du fichier a decompresser\n");
  243.   printf("destination: Nom du fichier decompresse\n");
  244. }
  245.  
  246. int main(argc,argv)
  247. /* Parametres en sortie: Renvoie un code d'erreur (0=Aucune)
  248.    Action: Procedure principale
  249.    Erreurs: Detectee, traitee et un code d'erreur est renvoye si necessaire
  250. */
  251. int argc;
  252. char *argv[];
  253. { if (argc!=3)
  254.      { aide();
  255.        exit(BAD_ARGUMENT);
  256.      }
  257.   else if ((f_source=fopen(argv[1],"rb"))==NULL)
  258.           { aide();
  259.             exit(BAD_FILE_NAME);
  260.           }
  261.        else if ((f_dest=fopen(argv[2],"wb"))==NULL)
  262.                { aide();
  263.                  exit(BAD_FILE_NAME);
  264.                }
  265.             else { decodagehuff();
  266.                    fclose(f_source);
  267.                    fclose(f_dest);
  268.                  }
  269.   printf("Execution de dcodhuff achevee.\n");
  270.   return (NO_ERROR);
  271. }
  272.